package greedy.prevClass.exer02;

import java.util.Scanner;

/**
 * 实验题目：最小跳数
 * 题目描述：
 * 给定一个非负整数数组，假定你的初始位置为数组第一个位置。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标位置，并且使用最少的跳跃次数。
 * 输入要求：
 * 输入一组非负整数数组，数组长度不超过500。
 * 输出要求：
 * 最少经过几次跳跃，可以到达最后一个位置。
 */
public class Main {
    public static void main(String[] args) {
        int[] arr = new int[501];
        int len = 0;
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            arr[len++] = sc.nextInt();
        }
        if (len == 1) {
            // 直接可以到达
            System.out.println(0);
            return;
        }
        int curIndex = 0;
        int maxIndex = arr[0];
        if (maxIndex >= len - 1) {
            // 可以在一步之内到达
            System.out.println(1);
            return;
        }
        int step = 0;
        while (curIndex <= maxIndex) {
            int nextMaxIndex = -1;
            for (int i = curIndex + 1; i <= maxIndex; i++) {
                nextMaxIndex = Math.max(nextMaxIndex, i + arr[i]); // 更新最大距离
                if (nextMaxIndex >= len - 1) {
                    System.out.println(step + 2);
                    return;
                }
            }
            curIndex = maxIndex;
            maxIndex = nextMaxIndex;
            step++;
        }
        System.out.println(-1);
    }
}
